from itertools import permutations


# （1）冒泡排序

def maopao(lst):
    n = len(lst)
    for i in range(n):
        for j in range(n - i - 1):
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]
    return lst


lst = [60, 5, 58, 15, 64, 17, 25, 3, 63, 76]
sorted_lst = maopao(lst)
print("冒泡排序：""排列前：", lst, "排列后：", sorted_lst)


# （2）选择排序
def xuanze(lst):
    n = len(lst)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if lst[j] < lst[min_idx]:
                min_idx = j
        lst[i], lst[min_idx] = lst[min_idx], lst[i]
    return lst


lst = [60, 5, 58, 15, 64, 17, 25, 3, 63, 76]
sorted_lst = xuanze(lst)
print("选择排序：""排列前：", lst, "排列后：", sorted_lst)


# (3)二分法查找

def erfenfa(lst, target):
    ind_lst = list(enumerate(lst))
    ind_lst.sort(key=lambda x: x[1])
    sorted_lst = [x[1] for x in ind_lst]
    left, right = 0, len(sorted_lst) - 1
    while left <= right:
        mid = (left + right) // 2
        if sorted_lst[mid] == target:
            return ind_lst[mid][0]
        elif sorted_lst[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1


lst = [60, 5, 58, 15, 64, 17, 25, 3, 63, 76]
target = 15
index = erfenfa(lst, target)
print("二分法查找：", "查找的列表是：", lst, "查找的元素是：", target, "在列表中的索引是：",
      index if index != -1 else "元素不在列表中")


# (4)不重复三位数
def unique_three_digit_numbers(digits):
    list_num = []
    total = 0
    for i in range(1, 5):
        for j in range(1, 5):
            for k in range(1, 5):
                if ((i != j) and (j != k) and (i != k)):
                    # 拼接为字符串
                    num = str(i) + str(j) + str(k)
                    # 写入列表
                    list_num.append(num)
                    total += 1
    return total, list_num


# 测试
digits = '1234'
count, list_num = unique_three_digit_numbers(digits)
print(f"能组成:{count}个互不相同且不重复的三位数,分别是:{list_num}")


# (5)斐波那契数列
def fibonacci(n):
    if n <= 0:
        return []
    elif n == 1:
        return [0]
    elif n == 2:
        return [0, 1]
    else:
        fib_seq = [0, 1]
        while len(fib_seq) < n:
            fib_seq.append(fib_seq[-1] + fib_seq[-2])
        return fib_seq


# 测试
n = 10  # 假设要求前10项
fib_numbers = fibonacci(n)
print(f"斐波那契数列的前{n}项是：{fib_numbers}")


# （6）素数
def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True


# 测试
primes = [num for num in range(100, 201) if is_prime(num)]
print(f"1到{n}的素数是：{primes}")


# (7)水仙花数
def is_armstrong_number(num):
    num_str = str(num)
    num_digits = len(num_str)
    sum_of_powers = sum(int(digit) ** num_digits for digit in num_str)
    return sum_of_powers == num


# 测试
start, end = 100, 999
armstrong_numbers = [num for num in range(start, end + 1) if is_armstrong_number(num)]
print(f"{start}到{end}之间的水仙花数是：{armstrong_numbers}")


# (8)完数
def is_perfect_number(num):
    divisors = [1]
    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            divisors.append(i)
            if i != num // i:
                divisors.append(num // i)
    return sum(divisors) == num


# 测试
limit = 1000
perfect_numbers = [num for num in range(1, limit + 1) if is_perfect_number(num)]
print(f"{limit}以内的所有完数是：{perfect_numbers}")


# （9）回文数
def is_palindrome(num):
    num_str = str(num)
    return num_str == num_str[::-1]


# 测试
start, end = 100, 99
palindromes = [num for num in range(start, end + 1) if is_palindrome(num)]
print(f"{start}到{end}之间的回文数是：{palindromes}")


# (10)
def longest(s):
    char_set = set()
    max_length = 0
    left = 0
    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_length = max(max_length, right - left + 1)
    return max_length


# 示例
s = "abcabcdbbbb"  # 无重复为abc
print("最长不重复子串长度为：", longest(s))


# (11)

def is_valid(s):
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}  # 正确的括号对应关系
    for char in s:
        if char in mapping:  # 如果字符是右括号
            top = stack.pop() if stack else '#'  # 弹出栈顶元素，如果栈为空则返回 '#'
            if mapping[char] != top:  # 如果栈顶元素不匹配当前右括号
                return False
        else:  # 如果字符是左括号
            stack.append(char)  # 将左括号压入栈中
    return not stack  # 如果栈为空，则所有括号都匹配成功


print("是否有效：", is_valid("()[]{}}{"))  # 输出: True


# (12) 反转字符串(不使用额外空间)
def reverse_string(s):
    left, right = 0, len(s) - 1
    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1
        return s


s = ["h", "e", "l", "l", "o"]
print("反转后的字符串为：", reverse_string(s))
s = ["H", "a", "n", "n", "a", "h"]
print("反转后的字符串为：", reverse_string(s))


# (13)生成杨辉三角的前一行
def y_h(Row):  # 定义一个函数 ，参数row
    if Row == 0:  # row行为0，输出空列表
        return []
    tri = [[1]]  # 第一行是1
    for i in range(1, Row):  # 循环生成每一行
        prev_row = tri[i - 1]  # 获取上一行
        current_row = [1]  # 初始化当前行
        for j in range(1, i):  # 计算中间元素
            current_row.append(prev_row[j - 1] + prev_row[j])
        current_row.append(1)  # 添加最后一个元素
        tri.append(current_row)  # 将元素添加到三角中
    return tri


# 示例
Row = 5  # 输出前五行
print("杨辉三角的前", Row, "行:", y_h(Row))


# (14)
def find_peak(nums):
    for i in range(1, len(nums) - 1):  # 循环范围是 1 到 len(nums) - 2
        if nums[i] > nums[i - 1] and nums[i] > nums[i + 1]:
            print("峰值索引为:", i)
    return -1  # return -1 是为了处理没有找到峰值的情况，确保函数在所有可能的输入下都有一个明确的返回值。


# 测试
print("峰值索引为:", find_peak([2, 4, 1, 2, 7, 8, 4, 1, 3, 5, 9, 4]))


def find_peak(nums):
    peak_index = -1  # 初始化峰值索引为 -1
    for i in range(1, len(nums) - 1):  # 遍历数组
        if nums[i] > nums[i - 1] and nums[i] > nums[i + 1]:
            peak_index = i  # 更新峰值索引
    return peak_index  # 返回最后一个峰值的索引


# 测试
print("峰值索引为:", find_peak([2, 4, 1, 2, 7, 8, 4, 1, 3, 5, 9, 4]))
